#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<time.h>
#include<mpi.h>
#include<omp.h>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>

using namespace std;

#define TAM_MAX_PALAVRA 100
#define TAM_ENCONTRADAS 40000
#define TAM_LOOP 1000

/* Faz o pré processamento do arquivo */
void PreProcessamento(){
	char c;
	FILE *fp, *fp_out;

	fp = fopen("palavras.txt", "r+");
	fp_out = fopen("palavras_out.txt", "w+");

	/* Apenas queremos letras e numeros, o resto vira _ */
	c = fgetc(fp);
	while(c != EOF){
		/* Se for diferente de letras, colocamos _ */
		if(!(c >= 'a' && c <= 'z') && !(c >= 'A' && c <= 'Z')){
			fputc('_', fp_out);
		} else {
			if(isupper(c))
				c = tolower(c);
			fputc(c, fp_out);
		}
		c = fgetc(fp);
	}

	fclose(fp);
	fclose(fp_out);
}

/* Esta função recebe um array de listas e um rank, para o rank 1 ela coloca palavras
 * de tamanho 1 em uma lista para o tank 2 coloca palavras de tamanho 2 em outra lista, 
 * e assim até o rank 5. Para todos os processos além da lista com tamanho igual ao seu
 * rank elas também terão na lista 0 as palavras com mais de 5 letras
 */
void separaListas(set<string> *palavras, int rank){
	char c, palavra[TAM_MAX_PALAVRA];
	int flag, i = 0;
	FILE *fp_out;

	fp_out = fopen("palavras_out.txt", "r+");

	/* Agora voltamos para o inicio do arquivo e separamos as palavras */
	c = fgetc(fp_out);
	while(c != EOF){
		if(c != '_') /* nosso delimitador é _ */
			palavra[i++] = c;
		else if (i != 0)
			flag = 1;

		if(flag == 1){
			palavra[i] = '\0';
			if(i > 5 && rank == 6){ 
				palavras[rank].insert(palavra);
			}
			else if(i == rank){
				palavras[rank].insert(palavra);
			}
			i = 0;
			flag = 0;
		}
		c = fgetc(fp_out);
	}

	fclose(fp_out);
}

/* Percorre a lista procurando a palavra aleatoria, se encontra então deleta a palavra da lista e retorna 1,
 * se não encontrar retorna 0. Também retorna 1 se a lista está vazia, pois não existe verificação a ser feita
 */
int procuraLista(set<string> *palavras, int rank, char palavra_aleatoria[]){
	int i;
	char palavra[TAM_MAX_PALAVRA];
	string aux;
	set<string>::iterator it;

	if(palavras[rank].empty() == true)
		return 0;
	
	for(it = palavras[rank].begin(); it != palavras[rank].end(); it++){
		aux = *it;

		/* Passamos a palavra de string (c++) para um array de chars (c) */
		for(i = 0; i < aux.size(); i++)
			palavra[i] = aux[i];
		palavra[i] = '\0';

		/* Vemos se achou a palavra, retorna 1 */
		if(!strcmp(palavra_aleatoria,palavra)){
			palavras[rank].erase(palavra_aleatoria);
			return 1;
		}

	}
	return 0;
}

/* Percorre a lista procurando a se alguma palavra tem dentro dela outra palavra já encontrada anteriormente,
 * se encontrar muda a palavra
 */
void procuraParte(set<string> *palavras, set<string> *palavrasFinal, int rank, char palavra[]){
	size_t inicio;
	string aux;
	set<string>::iterator it;

	if(palavras[rank].empty() == true)
		return;

	for(it = palavras[rank].begin(); it != palavras[rank].end(); it++){
			aux = *it;
			inicio = aux.find(palavra);

			if(inicio != string::npos && aux.size() > 5)
				(*palavrasFinal).insert(aux.erase(inicio,strlen(palavra)));
			else
				(*palavrasFinal).insert(aux);
	}
}

int main(int argc, char **argv){
	int i = 0, j = 0, k = 0, y = 0, num, tam, tempo = 0, pal = 0, aux_num_pal = 0;
	int cont[6], pal_aux;
	int rank, noProcesses, a, terminar = 1, sinal;
	char palavra_aleatoria[6], palavrasEncontradas[TAM_ENCONTRADAS][TAM_MAX_PALAVRA], aux_pal[TAM_MAX_PALAVRA], palavra[TAM_MAX_PALAVRA];
	int tamanho_total, tamanho_total_calculado = 0, tamanho_lista = 0;
	float porcentagem_obj, porcentagem_atual;
	time_t begin, end;

	/* Inicializamos MPI */
	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &noProcesses);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	MPI_Status Stat;

	set<string> palavras[7];
	set<string> palavrasFinal;
	set<string>::iterator it;
	string aux;	

	/* Verificação da porcentagem objetivo */
	if(argv[1] == NULL){
		cout << "Erro, nenhuma porcentagem objetivo foi indicada." << endl;
		exit(1);
	}
	else{
		sscanf(argv[1], "%f", &porcentagem_obj);
	}

	srand(time(NULL));

	/* Processo 0 faz o pré-processamento do arquivo */
	if(rank == 0){
		PreProcessamento();

		/* Da um boradcast para que os outros processos possam continuar */
		MPI_Bcast(&a, 1, MPI_INT, 0, MPI_COMM_WORLD);
	} else if (rank < 6){
		/* Esperam o processo mestre */
		MPI_Bcast(&a, 1, MPI_INT, 0, MPI_COMM_WORLD);

		separaListas(palavras, rank);
		
		/* Envia sinal para o mestre que está esperando a separação das listas */
		tam = 0;
		MPI_Send(&tam, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
		/* Envia tamanhos das listas para montar o tamanho total */
		tam = palavras[rank].size();
		MPI_Send(&tam, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
	} else if (rank == 6){
		/* Esperam o processo mestre */
		MPI_Bcast(&a, 1, MPI_INT, 0, MPI_COMM_WORLD);

		separaListas(palavras, rank);

		/* Envia tamanhos da lista para montar o tamanho total */
		tam = palavras[rank].size();
		MPI_Send(&tam, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
	}
	
	while(1){
		/* O processo 0 espera todos estarem prontos para começar a contar o tempo */
		if(rank == 0){
			/* O mestre espera a separação de todas as listas */
			tamanho_total_calculado = 0;
			for(k = 1; k < noProcesses-1; k++){
				MPI_Recv(&tamanho_lista, 1, MPI_INT, k, k, MPI_COMM_WORLD, &Stat);
				tamanho_total_calculado += tamanho_lista;
			}

			/* A lista de palavras com mais de 5 letras podem alterar quantas palavras no total devem ser procuradas */
			tamanho_total = 0;
			for(k = 1; k < noProcesses; k++){
				MPI_Recv(&tamanho_lista, 1, MPI_INT, k, k, MPI_COMM_WORLD, &Stat);
				tamanho_total += tamanho_lista;
			}

			/* Calculo para verificarmos qual a porcentagem de palavras foram encontradas */
			porcentagem_atual = ((double)tamanho_total_calculado/tamanho_total);
			cout << "Foram encontradas: " << (porcentagem_atual * 100) << "%" << endl;

			if(tempo != 1){
				time(&begin);
				tempo = 1;
			}

			/* Se encontrarmos mais do que queremos, mandamos um sinal para terminar, caso contrario continuamos */
			if((porcentagem_atual * 100) >= porcentagem_obj){
				time(&end);
				MPI_Bcast(&terminar, 1, MPI_INT, 0, MPI_COMM_WORLD);
				break;
			} else {
				MPI_Bcast(&sinal, 1, MPI_INT, 0, MPI_COMM_WORLD);
			}
		} else if (rank < 6){
			/* Esperam o processo mestre */
			MPI_Bcast(&sinal, 1, MPI_INT, 0, MPI_COMM_WORLD);
			
			/* Se o sinal é para terminar, saimos do loop */
			if(sinal == terminar) 
				break;

			#pragma omp parallel for \
			shared(palavras,palavrasEncontradas,pal_aux) private(j, i, num, palavra_aleatoria) reduction(+:pal)
			for(j = 0; j < TAM_LOOP; j++){
				if(palavras[rank].empty() == false){
					/* Gera uma palavra aleatoria do tamanho do processo atual */
					for(i = 0; i < rank; i++){
						num = 26 * (rand() / (RAND_MAX + 1.0));
						num = num + 97;
						palavra_aleatoria[i] = (char) num;
					}
					palavra_aleatoria[i] = '\0';

					/* Se encontra a palavra verificamos apagamos da lista */
					if(procuraLista(palavras, rank, palavra_aleatoria)){
							strcpy(palavrasEncontradas[pal++],palavra_aleatoria);
					}
				} else {
					j = TAM_LOOP;
				}
			}

			/* O rank 1 só lida com letras então não o usamos */
			if(rank > 1){
				/* Enviamos para o rank 6 as palavras que foram encontradas */
				MPI_Send(&pal, 1, MPI_INT, 6, rank, MPI_COMM_WORLD);
				for(k = 0; k < pal; k++)
					MPI_Send(&palavrasEncontradas[k][0], 100, MPI_CHAR, 6, k, MPI_COMM_WORLD);
			}

			/* Vai receber quantas palavras o nó 6 vai enviar */
			MPI_Recv(&tam, 1, MPI_INT, 6, rank, MPI_COMM_WORLD, &Stat);

			/* Recebemos as palavras */
			for(i = 0; i < tam; i++){
				MPI_Recv(&palavra[0], 100, MPI_CHAR, 6, rank, MPI_COMM_WORLD, &Stat);
				palavras[rank].insert(palavra);
			}

			/* Enviamos o numero de palavras encontradas */
			MPI_Send(&pal, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);

			/* Envia tamanhos das listas para montar o tamanho total */
			tam = palavras[rank].size() + pal;
			MPI_Send(&tam, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
		} else if (rank == 6) {
			/* Espera o processo mestre */
			MPI_Bcast(&sinal, 1, MPI_INT, 0, MPI_COMM_WORLD);

			/* Se o sinal é para terminar, saimos do loop */
			if(sinal == terminar) 
				break;

			/* Recebe dos processos 2 ao 5 as palavras encontradas e coloca em uma lista */
			for(k = 2; k < 6; k++){
				MPI_Recv(&aux_num_pal, 1, MPI_INT, k, k, MPI_COMM_WORLD, &Stat);
				for(y = 0; y < aux_num_pal; y++){
					MPI_Recv(&aux_pal[0], 100, MPI_CHAR, k, y, MPI_COMM_WORLD, &Stat);
					procuraParte(palavras, &palavrasFinal, rank, aux_pal);
					palavras[rank].swap(palavrasFinal);
					palavrasFinal.clear();
				}
			}

			if(palavras[rank].empty() == false){
				/* Verificamos quantas palavras vamos enviar para cada nó */
				for(k = 1; k <= 5; k++)
					cont[k] = 0;
				for(it = palavras[rank].begin(); it != palavras[rank].end(); it++){
					aux = *it;

					if(aux.size() >= 1 && aux.size() <= 5)
						cont[aux.size()]++;
				}

				for(k = 1; k <= 5; k++)
					MPI_Send(&cont[k], 1, MPI_INT, k, k, MPI_COMM_WORLD);

				/* Agora enviamos as palavras */
				for(it = palavras[rank].begin(); it != palavras[rank].end(); it++){
						aux = *it;

						for(i = 0; i < aux.size(); i++)
							palavra[i] = aux[i];
						palavra[i] = '\0';

						for(k = 1; k <= 5; k++)
							if(aux.size() == k)
								MPI_Send(&palavra, 100, MPI_CHAR, k, k, MPI_COMM_WORLD);

						if(aux.size() > 5)
							palavrasFinal.insert(palavra);
				}

				palavras[rank].swap(palavrasFinal);
				palavrasFinal.clear();
			}

			/* Envia tamanhos das listas para montar o tamanho total */
			tam = palavras[rank].size();
			MPI_Send(&tam, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
		}
	}

	if(rank == 0)
		cout << "Tempo decorrido: " << difftime(end,begin) << " segundos" << endl;

	MPI_Finalize();	

	return 0;
}
